A virtual memory system for virtually providing a memory space larger than a physical memory space that a main memory originally provides has been utilized so far. A computer to which the virtual memory system is applied has a data structure referred to as a page table including pairs of a virtual address and a physical address (hereinafter referred to as address translation pairs) in a main memory in order to translate a virtual address to a physical address. When address translation is desired, for example, when a virtual address is included in an instruction that a CPU (Central Processing Unit) which serves as a processor has fetched, the computer gains access to the main memory and executes the address translation with reference to the page table that the main memory holds.
However, much time is taken to refer to the page table in the main memory each time address translation is to be executed. Therefore, in general, the computer installs in the CPU a cache memory dedicated to address translation which is referred to as a TLB (Translation Lookaside Buffer) as an address translation buffer where some address translation pairs are held. The TLB is searched before referring to the page table in the main memory.
When the computer executes a memory access, first, the computer translates a virtual address to the corresponding physical address by using the TLB and then gains access directly to the memory using the physical address. Thus, the speed at which the TLB is accessed directly acts on the total speed at which the memory is accessed. In order to execute the address translation at a high speed, it is effective to reduce the capacity of the TLB to be searched. However, if the capacity of the TLB is too small, a virtual address to be translated may not find in the TLB a physical address to match (TLB miss) in many cases and the computer has to refer to the page table each time the TLB miss occurs. As a result, much time may be taken and the performance may be degraded.
In recent years, computer programs have used a large address area and hence the influence to the memory access has been increased than before when the capacity of TLB is small. On the other hand, the time taken for search may be increased if the capacity of the TLB is increased, which may hinder the improvement in the performance of hardware.
A full associative method and a set associative method are proposed as methods for referring to the TLB. The full associative method refers to the whole virtual address as a tag and the set associative method refers to a part of the virtual address as an index tag. A CAM (Content Addressable Memory) and a RAM (Random Access Memory) are given as memories for the TLB by way of example.
When adopting the full associative method, the CAM has been used as the memory that allows simultaneous search for a plurality of entries. When the CAM is used as the TLB, although the circuit size is increased, the TLB may be searched at a high speed even if the full associative method is employed.
When adopting the set associative method, the RAM has been used as the memory of the TLB. The RAM allows registration of many TLB entries with a relatively small size of mounting area of the TLB in the processor. However, only one entry is allowed to be referred to at a same time. In the set associative method, a part of the virtual address is referred to as the index tag and an entry which is specified with the index tag is read out of the memory, so that the TLB is searched at a high speed even if the RAM is used. However, in the set associative method, different virtual addresses having the same index part are registered into the same entry. Thus, when an access to the virtual addresses having the same index part is frequently gained, the entry may be overwritten and previous data may be lost. If multiple sets of index tags and multiple ways are used, the frequency at which the entry is overwritten is reduced in the set associative method in comparison with a direct mapping method having one set of index tags and one way. On the other hand, the frequency at which the entry is purged in the set associative method is higher than the frequency in the full associative method.
As described above, the TLB with the set associative method using the RAM and the TLB with the full associative method using the CAM have both merits and demerits and hence both the TLBs are frequently used in combination. If both the TLBs are to be used in combination, it may be desirable to register TLB entries necessary for important processing such as trap processing which is executed using a kernel of an OS (Operating System) into the TLB with the full associative method so as not to be purged from the TLB. In the full associative method, registration into an arbitrary entry is possible, and therefore as long as the maximum number of entries is checked, the TLB is controlled so that the TLB entry is not purged. The maximum number of entries is 16 or 32, for example.
[Patent Document 1] Japanese Laid-open Patent Publication No. 08-115262
[Patent Document 2] Japanese Laid-open Patent Publication No. 06-187244
[Patent Document 3] Japanese Laid-open Patent Publication No. 57-006956